#include <iostream>
#include <assert.h>
using namespace std;

template<typename T>
struct list_node{
  T _data;
  list_node<T> *_next;
  list_node<T> *_prev;

  list_node(const T &val = T())
   : _data(val),
   _prev(nullptr),
   _next(nullptr)
  {}

  //~list_node(){
  //  cout <<"~list_node()" <<endl;
  //}
};
//迭代器的*和->操作设计节点数据_data的存储类型，因此传T
//*和->操作涉及普通对象和const对象的权限问题，需要传入Ref和Ptr泛型返回值，普通对象传普通引用和普通指针；const对象传const引用和const指针。
//这里还要区分const list对象和const iterator对象。
template <class T, class Ref, class Ptr>
struct list_iterator{
  typedef list_node<T> Node;
  typedef list_iterator<T, Ref, Ptr> iterator;
  Node *_pnode;

  list_iterator(Node *pnode)
    :_pnode(pnode)
  {}

  //list_iterator的拷贝构造，析构，赋值重载使用默认生成的即可。

  Ref operator*() const{
    return _pnode->_data;
  }
  
  Ptr operator->() const{
    return &(operator*());
  }

  iterator& operator++(){
    _pnode = _pnode->_next;
    return *this;
  }

  iterator operator++(int){
    iterator it(*this);
    _pnode = _pnode->next;
    return it;
  }

  iterator& operator--(){
    _pnode = _pnode->_prev;
    return *this;
  }

  iterator operator--(int){
    iterator it(*this);
    _pnode = _pnode->_prev;
    return it;
  }

  bool operator!=(const iterator &it) const{
    return _pnode != it._pnode;
  }

  bool operator==(const iterator &it) const{
    return _pnode == it._pnode;
  }
};

template<typename T>
class Mylist{
 typedef list_node<T> Node;
 Node *_phead;
  public:
 typedef list_iterator<T, T&, T*> iterator;
 typedef list_iterator<T, const T&, const T*> const_iterator;

 iterator begin(){
   return iterator(_phead->_next);
 }
 iterator end(){
   return iterator(_phead);
 }

 const_iterator begin()const{
   return const_iterator(_phead->_next);
 }
 const_iterator end()const{
   return const_iterator(_phead);
 }

 void empty_initialize(){
   _phead = new Node;
   _phead->_next = _phead;
   _phead->_prev = _phead;
 }

 Mylist(){
   empty_initialize();
 }

template <class InputIterator>
 Mylist(InputIterator first, InputIterator last)
 {
   empty_initialize();
    while(first!=last)
    {
      push_back(*first);
      ++first;
    }
 }

void swap(Mylist<T> &mlt){
  std::swap(_phead, mlt._phead);
}

Mylist(const Mylist<T> &mlt){
  empty_initialize();
  Mylist<T> tmp(mlt.begin(), mlt.end());
  swap(tmp); 
}

Mylist<T>& operator=(Mylist<T> mlt){
  swap(mlt);
  return *this;
}

 ~Mylist(){
  clear();
  delete _phead;
 }

 void clear(){
   iterator it = begin();
   while(it != end())
   {
     it = erase(it);
   }
 }

 void push_back(const T &val){
   //Node *newnode = new Node(val);
   //Node *tail = _phead->_prev;
   //tail->_next = newnode;
   //newnode->_prev = tail;
   //newnode->_next = _phead;
   //_phead->_prev = newnode;
   insert(end(), val);
 }

 void push_front(const T &val){
   insert(begin(), val);
 }

 iterator insert(iterator pos, const T& val)
 {
   Node *newnode = new Node(val);
   Node *cur = pos._pnode;
   Node *prev = cur->_prev;

   prev->_next = newnode;
   newnode->_prev = prev;
   newnode->_next = cur;
   cur->_prev = newnode;
   return iterator(newnode);
 }

 iterator erase(iterator pos)
 {
   assert(pos != end());
   Node *cur = pos._pnode;
   Node *next = cur->_next;
   Node *prev = cur->_prev;
   next->_prev = prev;
   prev->_next = next;
   delete cur;
   return iterator(next);
 }

 void pop_back(){
   erase(--end());
 }

 void pop_front(){
   erase(begin());
 }
};

